package com.wtgroup.demo.leetcode.q664_奇怪的打印机;

import cn.hutool.core.util.RandomUtil;
import com.wtgroup.demo.common.judge.Judger;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author 60906
 * @date 2021/5/24 20:02
 */
public class Q664_T1 {

    @Test
    public void test1() {
        // String s = "aaabbb";
        // String s = "aba";
        String s = "tbgtgb";
        int res = new Solution_T1().strangePrinter(s);
        System.out.println(res);
        int res2 = new Solution_T2().strangePrinter(s);
        System.out.println(res2);
        // int res3 = new Solution_T3().strangePrinter(s);
        // System.out.println(res3);
        int res4 = new Solution_T4().strangePrinter(s);
        System.out.println(res4);
    }

    @Test
    public void test2() {
        new Judger(1000, ()->{
            String s = RandomUtil.randomString(RandomUtil.randomInt(0, 10));
            // System.out.println(s);
            int res1 = new Solution_T1().strangePrinter(s);
            // System.out.println(res1);
            // int res4 = new Solution_T4().strangePrinter(s);
            // System.out.println(res4);
            int res4_dp = new Solution_T4_Dp().strangePrinter(s);

            return res1 == res4_dp;
        }).start().print();
    }



    /**递归尝试 v1
     * [超时]
     * 17 / 200 个通过测试用例.
     */
    class Solution_T1 {
        /*
         * 当前位置 index 是否相等, 相等, 本次字符无需打印. 否则打印, 1~N-index 个尝试.
         * 剩下的, 扔进递归, 返回最小打印次数.
         * */

        public int strangePrinter(String s) {
            if (s.isEmpty()) {
                return 0;
            }
            char[] prints = new char[s.length()];
            return func(s, 0, prints);
        }

        private int func(String s, int index, char[] prints) {
            if (index == s.length()) {
                return 0;
            }

            char curr = s.charAt(index);
            if (curr == prints[index]) {
                // 相等, 不用打印
                return func(s, index + 1, Arrays.copyOf(prints, prints.length));
            }

            // 需要打印: 1~N-index 挨个尝试
            int ans = Integer.MAX_VALUE;
            for (int i = index; i < s.length(); i++) {
                Arrays.fill(prints, index, i + 1, curr); // 一股脑填充, 防止递归里改了某些位置
                ans = Math.min(func(s, index + 1, Arrays.copyOf(prints, prints.length)) + 1, ans);
                // Arrays.fill(prints, i+1, prints.length, '0'); // 状态重置
            }

            return ans;
        }
    }

    /**
     * 转成动归失败.
     * 递归尝试太麻烦了.
     */
    class Solution_T2 {
        /*
         * 当前位置 index 是否相等, 相等, 本次字符无需打印. 否则打印, 1~N-index 个尝试.
         * 剩下的, 扔进递归, 返回最小打印次数.
         * */

        public int strangePrinter(String s) {
            if (s.isEmpty()) {
                return 0;
            }
            return func(s);
        }

        private int func(String s) {
            int N = s.length();
            int[] dp = new int[N + 1];

            dp[N] = 0;
            char[] prints = new char[s.length()];

            for (int index = N - 1; index >= 0; index--) {
                char curr = s.charAt(index);
                if (curr == prints[index]) {
                    // 相等, 不用打印
                    // return func(s, index + 1, Arrays.copyOf(prints, prints.length));
                    dp[index] = dp[index + 1];
                } else {
                    // 需要打印: 1~N-index 挨个尝试
                    dp[index] = Integer.MAX_VALUE;
                    for (int i = index; i < N; i++) {
                        Arrays.fill(prints, index, i + 1, curr); // 一股脑填充, 防止递归里改了某些位置
                        // ans = Math.min(func(s, index + 1, Arrays.copyOf(prints, prints.length)) + 1, ans);
                        dp[index] = Math.min(dp[index + 1] + 1, dp[index]);
                        // Arrays.fill(prints, i+1, prints.length, '0'); // 状态重置
                    }
                }
            }

            return dp[0];
        }
    }


    // class Solution_T3 {
    //     /*
    //      * i 位置如果前面有相同字符(j位置)刚好打印过来了, 那么本次不用打印.
    //      * 递归里, 限制条件: i 之前都是 j , 后面遇到和 j 不同的必须要打印一次.
    //      * */
    //     public int strangePrinter(String s) {
    //         return func(s, 0, -1);
    //     }
    //
    //     /**
    //      * @param s
    //      * @param index    当前字符
    //      * @param printSeq 当前位置前面打印机连续打印的字符下标
    //      * @return
    //      */
    //     private int func(String s, int index, int printSeq) {
    //         int N = s.length();
    //         if (index == N) {
    //             return 0;
    //         }
    //
    //         int ans = Integer.MAX_VALUE;
    //         char currChar = s.charAt(index);
    //
    //         if (printSeq > 0 && currChar == s.charAt(printSeq)) {
    //             // 当前有可能无需打印: 前面的字符打印时顺延到当前位置, 这里就选择不打印, 因为打印对全局没有影响
    //             ans = 0 + func(s, index + 1, printSeq);
    //         } else {
    //             // 必须打印, 否则当前位置永无可能是当前字符
    //             // 1) 打印一次; 2) 连续打印
    //             ans = Math.min(1 + func(s, index + 1, printSeq), ans);
    //             ans = Math.min(1 + func(s, index + 1, index), ans);
    //         }
    //
    //         return ans;
    //     }
    // }

    /**看LC题解提示, 写的递归尝试 v2
     * [超时]
     * 51 / 200
     */
    class Solution_T4 {
        /*
        * base case: 单个字符; 首位一样的; 不一样的.
        * k 分割, 前半段最少次数+后半段最少次数
        * */

        public int strangePrinter(String s) {
            int N = s.length();

            return func(s, 0, N-1);
        }

        private int func(String s, int left, int right) {
            if (left == right) {
                return 1;
            }
            if (s.charAt(left) == s.charAt(right)) {
                // 首尾相等, 尾部不用考虑
                return func(s, left, right - 1);
            }

            // 首尾不等, 二分尝试
            int ans = Integer.MAX_VALUE;
            for (int k = left; k < right; k++) {
                // left~k, k+1~right
                int cnt = func(s, left, k) + func(s, k + 1, right);
                ans = Math.min(ans, cnt);
            }

            return ans;
        }
    }

    /**
     * 和题解答案一致
     */
    class Solution_T4_Dp {
        /*
         * base case: 单个字符; 首位一样的; 不一样的.
         * k 分割, 前半段最少次数+后半段最少次数
         * */

        public int strangePrinter(String s) {
            return func(s);
        }

        private int func(String s) {
            int N = s.length();
            int[][] dp = new int[N][N];
            // left 行, right 列, 左下半边都是 0 . 对角线 1.
            // 根据依赖关系, \ 对角线填充, 左下到左上
            // 只管左上半角, 从下到上, 从左到右
            for (int left = N-1; left >= 0; left--) {
                dp[left][left] = 1; // left == right: 1
                for (int right = left + 1; right < N; right++) {
                    if (s.charAt(left) == s.charAt(right)) {
                        // 首尾相等, 尾部不用考虑
                        dp[left][right] = dp[left][right - 1];
                    } else {
                        // 首尾不等, 二分尝试
                        int ans = Integer.MAX_VALUE;
                        for (int k = left; k < right; k++) {
                            // left~k, k+1~right
                            int cnt = dp[left][k] + dp[k+1][right];
                            ans = Math.min(ans, cnt);
                        }
                        dp[left][right] = ans;
                    }
                }
            }

            return dp[0][N-1];
        }
    }
}
